using System.Collections.Generic;

namespace GameEngine.Collections.Generic
{
	public class BinaryHeap<T>
	{
		private List<T> list;
		private IComparer<T> comparer;
		public BinaryHeap(IComparer<T> comparer)
		{
			this.list = new List<T>();
			this.comparer = comparer;
		}

		public void Insert(T item)
		{
			list.Add(item);
			int index = list.Count - 1;
			while (index > 0)
			{
				int parentIndex = (index - 1) / 2;
				T parentItem = this.list[parentIndex];
				if (this.comparer.Compare(parentItem, item) < 0)
				{
					break;
				}
				this.list[index] = parentItem;
				index = parentIndex;
			}
			this.list[index] = item;
		}

		public bool Remove(out T result)
		{
			int count = this.list.Count - 1;
			if (count < 0)
			{
				result = default(T);
				return false;
			}
			result = this.list[0];
			this.list[0] = this.list[count];
			this.list.RemoveAt(count);
			int index = 0;
			do
			{
				int leftIndex = 2 * index + 1;
				int rightIndex = leftIndex + 1;
				int largestIndex = index;
				if (leftIndex < count && this.comparer.Compare(this.list[leftIndex], (this.list[index])) < 0)
				{
					largestIndex = leftIndex;
				}
				if (rightIndex < count && this.comparer.Compare(this.list[rightIndex], (this.list[largestIndex])) < 0)
				{
					largestIndex = rightIndex;
				}
				if (largestIndex == index)
				{
					break;
				}
				else
				{
					T temp = this.list[index];
					this.list[index] = this.list[largestIndex];
					this.list[largestIndex] = temp;
					index = largestIndex;
				}
			}
			while (true);
			return true;
		}
	}
}
